package doublelinkedlist

import (
    "fmt"

    myErr "data_structure/error"
)

type node[T any] struct {
    data       T
    prev, next *node[T]
}

type doublyLinkedList[T any] struct {
    head, tail *node[T]
    length     uint
}

func New[T any]() *doublyLinkedList[T] {
    head := new(node[T])
    tail := new(node[T])
    head.next = tail
    tail.prev = head
    return &doublyLinkedList[T]{
        head:   head,
        tail:   tail,
        length: 0,
    }
}

func (dl *doublyLinkedList[T]) Length() uint {
    return dl.length
}

func (dl *doublyLinkedList[T]) IsEmpty() bool {
    return dl.length == 0
}

func (dl *doublyLinkedList[T]) Clear() {
    dl.head.next = dl.tail
    dl.tail.prev = dl.head
    dl.length = 0
}

func (dl *doublyLinkedList[T]) GetByIndex(index uint) (*node[T], error) {
    if index > dl.length {
        return nil, myErr.ErrorIndexOutOfRange
    }

    var node *node[T]
    if index <= dl.length/2 {
        node = dl.getFromHead(index)
    } else {
        node = dl.getFromTail(index)
    }
    return node, nil
}

func (dl *doublyLinkedList[T]) getFromHead(index uint) *node[T] {
    node := dl.head
    for i := 0; i < int(index); i++ {
        node = node.next
    }
    return node
}

func (dl *doublyLinkedList[T]) getFromTail(index uint) *node[T] {
    node := dl.tail
    for i := dl.length; i >= index; i-- {
        node = node.prev
    }
    return node
}

func (dl *doublyLinkedList[T]) Append(data T) {
    newNode := &node[T]{data: data}
    prev := dl.tail.prev
    prev.next = newNode
    newNode.prev = prev
    dl.tail.prev = newNode
    newNode.next = dl.tail
    dl.length++
}

func (dl *doublyLinkedList[T]) Insert(index uint, data T) error {
    if index > dl.length+1 || index == 0 {
        return myErr.ErrorIndexOutOfRange
    }
    preNode, err := dl.GetByIndex(index - 1)
    if err != nil {
        return err
    }
    nextNode := preNode.next
    newNode := &node[T]{data: data}
    preNode.next = newNode
    newNode.prev = preNode
    newNode.next = nextNode
    nextNode.prev = newNode
    dl.length++
    return nil
}

func (dl *doublyLinkedList[T]) Remove(index uint) (*node[T], error) {
    if index > dl.length || index == 0 {
        return nil, myErr.ErrorIndexOutOfRange
    }

    currentNode, err := dl.GetByIndex(index)
    if err != nil {
        return nil, err
    }
    preNode := currentNode.prev
    nextNode := currentNode.next
    preNode.next = nextNode
    nextNode.prev = preNode
    currentNode.next = nil
    currentNode.prev = nil
    dl.length--
    return currentNode, nil
}

func (dl *doublyLinkedList[T]) String() string {
    str := "<head>"
    if dl.length != 0 {
        node := dl.head.next
        for node.next != nil {
            str += "<->" + fmt.Sprintf("%v", node.data)
            node = node.next
        }
    }
    str += fmt.Sprintf("<-><tail> length: %d", dl.length)
    return str
}
